package com.example.demo.leetcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 链接：<a href="https://leetcode.cn/problems/first-completely-painted-row-or-column/description/">https://leetcode.cn/problems/first-completely-painted-row-or-column/description/</a><br>
 * 题目:<br>
 * 给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1，m * n] 内的 所有 整数。<br>
 * 从下标 0 开始遍历 arr 中的每个下标 i ，并将包含整数 arr[i] 的 mat 单元格涂色。<br>
 * 请你找出 arr 中第一个使得 mat 的某一行或某一列都被涂色的元素，并返回其下标 i 。<br>
 * <p>
 * 提示：
 * <p>
 * m == mat.length<br>
 * n = mat[i].length<br>
 * arr.length == m * n<br>
 * 1 <= m, n <= 105<br>
 * 1 <= m * n <= 105<br>
 * 1 <= arr[i], mat[r][c] <= m * n<br>
 * arr 中的所有整数 互不相同<br>
 * mat 中的所有整数 互不相同<br>
 *
 *
 * <p>
 * <p>
 * 翻译成人话：<br>
 * 按照arr数组从左到右的顺序遍历各个arr[i]，涂抹这个值在矩阵中对应位置的网格，一旦你发现它所在的行或者列满员了，就返回这个i。
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/01/29 13:51
 */
public class _2661_找出叠涂元素 {


    public static void main(String[] args) {
        int[] arr = {2, 8, 7, 4, 1, 3, 5, 6, 9};
        int[][] mat = {{3, 2, 5}, {1, 4, 6}, {8, 7, 9}};
        int i = firstCompleteIndex(arr, mat);
    }

    /**
     * 超出时间限制
     *
     * @author WangYX
     * @date 2024/01/29 14:26
     */
    public static int firstCompleteIndex(int[] arr, int[][] mat) {
        //把矩阵中数字对应的下标放到Map中
        Map<Integer, Region> map = new HashMap<>();
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[i].length; j++) {
                map.put(mat[i][j], new Region(i, j));
            }
        }

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            if (!set.contains(arr[i])) {
                set.add(arr[i]);
            }
            //判断元素所在的行和列是否被涂色
            Region region = map.get(arr[i]);
            //行
            boolean row = true;
            for (int j = 0; j < mat[0].length; j++) {
                if (!set.contains(mat[region.row][j])) {
                    row = false;
                    break;
                }
            }
            //列
            boolean col = true;
            for (int j = 0; j < mat.length; j++) {
                if (!set.contains(mat[j][region.col])) {
                    col = false;
                    break;
                }
            }
            if (row || col) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 区域
     */
    private static class Region {
        /**
         * 行
         */
        Integer row;

        /**
         * 列
         */
        Integer col;

        public Region(Integer row, Integer col) {
            this.row = row;
            this.col = col;
        }
    }

    /**
     * 官解：<br>
     * 由于矩阵 mat 中每一个元素都不同，并且都在数组 arr 中，所以首先我们用一个哈希表来存储 mat 中每一个元素的位置信息（即行列信息）。然后用一个长度为 n 的数组 rowCnt 来表示每一行中已经被涂色的个数，用一个长度为 m 的数组 colCnt 来表示每一列中已经被涂色的个数，其中若出现某一行 i 有 rowCnt[i]=m 或者某一列 j 有 colCnt[j]=n，则表示第 i 行或 j 列已被全部涂色。<br>
     * <p>
     * 接着我们遍历数组 arr，对于遍历到的 arr[i]，从哈希表中得到该元素的行列信息，并更新数组 rowCnt 和 colCnt，如果出现某一行或某一列被全部涂色，则返回该元素的下标 i
     *
     * @author WangYX
     * @date 2024/01/29 14:27
     */
    public int firstCompleteIndex1(int[] arr, int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                map.put(mat[i][j], new int[]{i, j});
            }
        }
        int[] rowCnt = new int[n];
        int[] colCnt = new int[m];
        for (int i = 0; i < arr.length; ++i) {
            int[] v = map.get(arr[i]);
            ++rowCnt[v[0]];
            if (rowCnt[v[0]] == m) {
                return i;
            }
            ++colCnt[v[1]];
            if (colCnt[v[1]] == n) {
                return i;
            }
        }
        return -1;
    }


}
